package com.lcz.suanfa;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * <pre>
 * <img width="128" height="110" src="https://tse3-mm.cn.bing.net/th/id/OIP-C.en-w_oH-yn2UsSRfWnOsGAHaGY?w=198&h=180&c=7&r=0&o=5&dpr=1.25&pid=1.7" alt="马刺">
 * 作者:     <a href="https://github.com/liuchuanzheng">刘传政</a>
 * 创建时间:  9:46 2022/2/16 0016
 * QQ:      1052374416
 * 电话:     18501231486
 * 描述:
 * </pre>
 */
public class Suanfa_链表 {
    @Test
    public void test() {

    }

    //删除链表中的节点
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }


    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    @Test
    public void test_删除链表的倒数第N个节点() {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        node1.next = node2;
        ListNode node = removeNthFromEnd(node1, 1);

    }

    //删除链表的倒数第N个节点
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int lianbiaoCount = 0;
        ListNode current = head;

        while (current != null) {
            lianbiaoCount++;
            current = current.next;
        }
        if (lianbiaoCount == 1) {
            return null;
        }
        ListNode find = head;
        int count = lianbiaoCount - n;
        while (count >= 1) {
            find = find.next;
            count--;
        }
        if (n == 1) {
            //找到前一个节点
            current = head;
            while (current.next != null && current.next != find) {
                current = current.next;
            }
            current.next = null;
        } else {
            find.val = find.next.val;
            find.next = find.next.next;
        }


        return head;
    }

    //反转链表
    public ListNode reverseList(ListNode head) {
        ArrayList<ListNode> list = new ArrayList();
        ListNode temp = head;
        while (temp != null) {
            list.add(temp);
            temp = temp.next;
        }
        ListNode newHead = new ListNode(1);
        ListNode currentNode = null;
        for (int i = list.size() - 1; i >= 0; i--) {
            ListNode node = list.get(i);
            if (i == list.size() - 1) {
                newHead.next = node;
            }
            if (currentNode != null) {
                currentNode.next = node;
            }
            currentNode = node;
            if (i == 0) {
                node.next = null;
            }
        }
        return newHead.next;
    }

    public ListNode reverseList2(ListNode head) {
        ListNode pre = null;
        ListNode next = null;
        ListNode current = head;
        while (current != null) {
            current.next = pre;
            pre = current;
            current = current.next;
        }
        return pre;
    }

    public int nodeCount(ListNode head) {
        int count = 0;
        ListNode current = head;

        while (current != null) {
            count++;
            current = current.next;
        }
        return count;
    }

    @Test
    public void test_合并两个有序链表() {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(4);
        node1.next = node2;
        node2.next = node3;

        ListNode node4 = new ListNode(1);
        ListNode node5 = new ListNode(3);
        ListNode node6 = new ListNode(4);
        node4.next = node5;
        node5.next = node6;
        ListNode node = mergeTwoLists(node1, node4);
        ListNode current = node;
        while (current != null) {
            System.out.println(current.val);
            current = current.next;
        }

    }

    //合并两个有序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }

        int count1 = nodeCount(list1);
        int count2 = nodeCount(list2);
        int current1 = list1.val;
        int current2 = list2.val;

        ListNode temp1 = list1;
        ListNode temp2 = list2;
        ListNode total = new ListNode(1);
        ListNode currentNode = null;
        int totalcount = 1;
        while (totalcount < (count1 + count2 + 1)) {

            if (temp1 != null) {
                current1 = temp1.val;
            } else {
                current1 = Integer.MAX_VALUE;
            }
            if (temp2 != null) {
                current2 = temp2.val;
            } else {
                current2 = Integer.MAX_VALUE;
            }
            ListNode minNode = null;
            if (current1 <= current2) {
                minNode = temp1;
                if (temp1 != null) {
                    temp1 = temp1.next;
                }

            } else {
                minNode = temp2;
                if (temp2 != null) {
                    temp2 = temp2.next;
                }
            }
            if (total.next == null) {
                total.next = minNode;
            }
            if (currentNode != null) {
                currentNode.next = minNode;
            }
            currentNode = minNode;
            totalcount++;

        }
        return total.next;
    }

    //回文链表
    public boolean isPalindrome(ListNode head) {
        ArrayList<Integer> listNodes = new ArrayList<>();
        ListNode current = head;

        while (current != null) {
            listNodes.add(current.val);
            current = current.next;
        }
        for (int i = 0; i < listNodes.size(); i++) {
            if (listNodes.get(i) != listNodes.get(listNodes.size() - 1 - i)) {
                return false;
            }
        }
        return true;
    }
    //环形链表
    public boolean hasCycle(ListNode head) {
        ListNode current = head;
        HashSet<ListNode> set = new HashSet();
        while (current != null) {
            if (!set.add(current)) {
                return true;
            }
            current = current.next;
        }
        return false;
    }
}
